寒假又开始刷题了。顺便写写题解。
题目传送门
思路
看到第一眼就知道这题该拆成两个步骤：
- 求出b的目标排序；
- 求得到排序需要的交换次数。
前置知识
排序不等式
排序不等式指出:
以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。与很多不等式不同，排序不等式不需限定 $x_i, y_i$ 的正负。
离散化
离散化，就是当我们只关心数据的大小关系时，用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考虑将其离散化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| struct Data {
int idx, val;
bool operator < (const Data& o) const {
if (val == o.val) return idx < o.idx;
return val < o.val;
}
} tmp[maxn];
for (int i = 1; i <= n; ++i)
tmp[i] = (Data){i, arr[i]};
std::sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; ++i)
arr[tmp[i].idx] = i;
|
求逆序对
归并排序
归并排序大概是运用了分治的思想。对于一个未排序的数组，归并排序将其分为左右两个子数组，分别将其排序，最后进行合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void merge_sort(int s, int t) {
int mid = s + (t - s >> 1);
merge_sort(s, mid);
merge_sort(mid + 1, t);
int b[MAXN], l = s, r = mid + 1, k = s;
while(l <= mid && r <= t) {
if(arr[l] < arr[r]) {
b[k++] = arr[l++];
}
else b[k++] = arr[r++];
}
for(;l <= mid; ++l) b[k++] = arr[l];
for(;r <= t; ++r) b[k++] = arr[r];
for(int i = s; i <= t; ++i) {
arr[i] = b[i];
}
}
|
归并排序求逆序对
对于一个数组的一次合并操作，此时数组的两个部分（s~mid）和（mid+1~t）都已经排好序。如果需要将数组的第r(mid < r <= t)个元素放入b的第k个位置，则说明他需要与未放进数组b的从i到mid共mid - l + 1个元素交换，即交换mid - l + 1次。
因此，我们只需要在代码中添加一行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void merge_sort(int s, int t) {
if(s == t) return;
int mid = s + (t - s >> 1)， res;
merge_sort(s, mid);
merge_sort(mid + 1, t);
int b[MAXN], l = s, r = mid + 1, k = s;
while(l <= mid && r <= t) {
if(arr[l] < arr[r]) {
b[k++] = arr[l++];
}
else {
b[k++] = arr[r++];
res += mid - l + 1;
}
}
for(;l <= mid; ++l) b[k++] = arr[l];
for(;r <= t; ++r) b[k++] = arr[r];
for(int i = s; i <= t; ++i) {
arr[i] = b[i];
}
}
|
树状数组求逆序对
先鸽了
做法
由排序不等式，我们知道
显然，当数组a、b 排序顺序相同时，该式最小。
首先对a、b数组离散化，用c数组记录数字在a中的位置（即c[a[i]] = i）,然后令b[i] = c[b[i]]，得到b离a顺序的差距。
要求最小的交换次数，注意到在a交换和在b交换其实是等价的，所以只需要求变换后的b中的逆序对，这里用归并排序做。
$AC\ Code:$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
const int mod = 1e8 - 3;
int a[MAXN], b[MAXN], c[MAXN];
long long ans = 0;
struct Data {
int val;
int idx;
bool operator < (const Data &a) const {
if(a.val == val)
return idx < a.idx;
return val < a.val;
}
}tmp[MAXN], tmq[MAXN];
void merge_sort(int s, int t) {
if(s == t) return;
int mid = s + (t - s >> 1);
merge_sort(s, mid);
merge_sort(mid + 1, t);
int tmp[MAXN];
int k = s, l = s, r = mid + 1;
while(l <= mid && r <= t) {
if(b[l] < b[r]) {
tmp[k++] = b[l++];
}
else {
tmp[k++] = b[r++];
ans += mid - l + 1;
ans %= mod;
}
}
while(l <= mid) tmp[k++] = b[l++];
while(r <= t ) tmp[k++] = b[r++];
for(int i = s; i <= t; ++i) b[i] = tmp[i];
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= n; ++i) cin >> b[i];
for(int i = 1; i <= n; ++i) {
tmp[i] = (Data){a[i], i};
tmq[i] = (Data){b[i], i};
}
sort(tmp + 1, tmp + 1 + n);
sort(tmq + 1, tmq + 1 + n);
for(int i = 1; i <= n; ++i) {
a[tmp[i].idx] = i;
b[tmq[i].idx] = i;
}
for(int i = 1; i <= n; ++i) c[a[i]] = i;
for(int i = 1; i <= n; ++i) b[i] = c[b[i]];
merge_sort(1, n);
cout << ans % mod<< endl;
return 0;
}
|
一点总结：
这题用到了很多技巧，如离散化、逆序对，是一道比较综合的题目。（我一遍查资料一边做了好久才做出来）
